\section{索引}
\begin{definition}[索引]
	在一组记录集合中找到关键码值等于给定值的某个记录,或者找到关键码值符合特定条件的某些记录的过程。
\end{definition}
\textbf{提高检索效率的方法：}
\begin{itemize}
	\item 预排序
	\item 建立索引
	\item 散列技术
\end{itemize}
\begin{definition}[关键码的比较]
	检索运算的主要操作。
\end{definition}
\begin{definition}[平均检索长度(ASL)]
	检索过程中对关键码的平均比较次数，衡量检索算法优劣的时间标准：
	\begin{equation}
		ASL = \sum_{i=1}^nP_iC_i
	\end{equation}
	这里$P_i$为检索第i各元素的概率，$C_i$为找到第i个元素所需要的关键吗值和给定值的比较次数。
\end{definition}
\textbf{顺序检索：}针对线性表里的所有记录,逐个进行关键码和给定值的比较。如果某个记录的关键码和给定值比较相等，则检索成功否则检索失败。可以顺序存储，链接。
\textbf{监视哨顺序检索算法}
\begin{cpp}
template <typename Type>
class Item {
private:
  Type key;   // 关键码域
  // 其它域
  public:
    Item(Type value):key(value) {}
    Type getKey() {return key;}        // 取关键码值
    void setKey(Type k){ key=k;}    // 置关键码
};
vector<Item<Type>*> dataList;
template <typename Type> int SeqSearch(vector<Item<Type>*>& dataList, int
length, Type k) {
  int i=length;
  dataList[0]->setKey (k);    // 将第0个元素设为待检索值,设监视哨
  while(dataList[i]->getKey()!=k) i--;
  return i;    // 返回元素位置
}
\end{cpp}
检索成功：假设检索每个关键码等概率$P_i=\frac{1}{n}$
\begin{equation*}
	\sum_{i=0}^{n-1}P_i\cdot(n-i)=\frac{1}{n}\sum_{i=0}^{n-1}(n-i)=\sum_{i=1}^n i=\frac{n+1}{2}
\end{equation*}
检索失败：假设检索失败时都需要比较n+1此（设置了一个监视哨）

假设检索成功的概率为p，检索失败的概率为q=(1-p)
\[ASL=p\cdot\frac{n+1}{2}+q\cdot(n+1)=(n+1)(1-p/2)\]
$(n+1)/2<ASL<(n+1)$
顺序检索的优点：插入元素可以直接加在表尾$\Theta(1)$,缺点：检索时间太长$\Theta(n)$

\begin{definition}[二分检索]
	将任一元素 dataList[i] .Key 与给定值 K 比较。
\end{definition}
三种情况:
\begin{itemize}
	\item Key = K,检索成功,返回 dataList[i]
	\item Key > K,若有则一定排在 dataList[i]前
	\item Key < K,若右则一定排在 dataList[i]后
\end{itemize}
进一步缩小范围。
\begin{cpp}
template <Typename Type> int BinSearch (vector<Item<Type>*>&
dataList, int length, Type k){
  int low=1, high=length, mid;
  while (low<=high) {
    mid=(low+high)/2;
    if (k<dataList[mid]->getKey())
      high = mid-1;// 右缩检索区间
    else if (k>dataList[mid]->getKey())
      low = mid+1;// 左缩检索区间
    else return mid;// 成功返回位置
  }
return 0;    // 检索失败,返回0
}
\end{cpp}
\begin{figure}
	\centering
	% \includegraphics[width=0.5\textwidth]{index02}
	\includesvg[width=0.5\textwidth]{binary_search}
	\caption{二分检索示意图}
\end{figure}
\begin{itemize}
	\item 第一次:l=1, h=9, mid=5; array[5]=35>18
	\item 第二次:l=1, h=4, mid=2; array[2]=17<18
	\item 第三次:l=3, h=4, mid=3; array[3]=18=18
\end{itemize}
二分检索性能分析：
\begin{itemize}
	\item 最大检索长度$\lceil log_2(n+1)\rceil$
	\item 失败检索长度是：$log_2(n+1)$
	\item 成功的平均检索长度为：
	      \[ASL=\frac{1}{n}(\sum_{i=1}^j i\cdot2^{i-1})=\frac{n+1}{n}log_2(n+1)-1\approx log_2(n+1)-1\quad(n>50)\]
\end{itemize}
\begin{itemize}
	\item[优点：]平均和最大检索长度相近，检索速度快。
	\item[缺点：]要排序，顺序存储，不容易更新（插入/删除）。
\end{itemize}
\subsection{分块检索的思想}
\begin{itemize}
	\item  设线性表中共有 n 个数据元素,将表分成 b 块
	\item  前一块最大关键码必须小于后一块最小关键码
	\item  每一块中的关键码不一定有序
\end{itemize}
分块有序：顺序与二分法的折衷既有较快的检索又有较灵活的更改。
\begin{figure}[H]
	\centering
	% \includegraphics[width=\textwidth]{index03}
	\includesvg[width=\textwidth]{block_range_search}
	\caption{分块检索}
\end{figure}
分块检索为两级检索：
\begin{itemize}
	\item 先在索引表中确定待查元素所在的块 $ASL_b$
	\item 然后在块内检索待查的元素 $ASL_w$
\end{itemize}
\[ASL=ASL_b+ASL_w\approx log_2(b+1)-1+(s+1)/2\approx\log_2(1+n/s)+s/2\]
假设在索引表中用顺序检索，在块内也使用顺序检索：
\begin{align}
	ASL_b=\frac{b+1}{2}                                \\
	ASL_w=\frac{s+1}{2}                                \\
	ASL & =\frac{b+1}{2}+\frac{s+1}{2}=\frac{b+s}{2}+1 \\
	    & =\frac{n+s^2}{2s}+1
\end{align}
当$s=\sqrt{n}$时ASL取最小值：$ASL=\sqrt{n}+1\approx\sqrt{n}$。当 n=10,000 时：
\begin{itemize}
	\item 顺序检索 5,000 次
	\item 二分法检索 14 次
	\item 分块检索 100 次
\end{itemize}
\textbf{分块检索优缺点：}
\begin{itemize}
	\item 优点:插入、删除相对较易。没有大量记录移动。
	\item 缺点:增加一个辅助数组的存储空间。初始线性表分块排序。当大量插入/删除时,或结点分布不均匀时，速度下降。
\end{itemize}
\subsection{集合检索}
\begin{definition}[集合(set)]:由若干个确定的、不同的对象构成的整体。
\end{definition}
\begin{definition}[集合的检索：]确定一个值是不是某一个集合的元素。
\end{definition}
\begin{table}[H]
	\centering
	\caption{集合操作}
	\begin{tabular}{llll}
		\toprule
		                         & {运算名称} & 数学符号        & 计算机运算符号   \\
		\midrule
		\multirow{5}{2cm}{算术运算符} & 并      & $\cup$      & *,\&,AND  \\
		                         & 差      & -           & -         \\
		                         & 交      & $\cap$      & $*,\&AND$ \\
		                         & 相等     & =           & 并==       \\
		                         & 不等     & $\neq$      & $!=$      \\
		\midrule
		\multirow{5}{2cm}{逻辑运算}  & 包含于    & $\subset$   & <=        \\
		                         & 包含     & $\supseteq$ & >=        \\
		                         & 真包含于   & $\subset$   & <         \\
		                         & 真包含    & $\subset$   & >         \\
		                         & 属于     & $\in$       & IN,at     \\
		\bottomrule
	\end{tabular}
\end{table}
\textbf{集合的抽象数据类型}
\begin{cpp}
template<size_t N>// N为集合的全集元素个数
\end{cpp}
\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{set01}
	\caption{用位向量表示集合}
\end{figure}
\begin{figure}[H]
	\centering
	\includesvg[width=\textwidth]{bit_vector_collection}
	\caption{计算0-15之间的素奇数}
\end{figure}
\begin{cpp}
typedef unsigned long ulong;
enum {
  // unsigned long数据类型的位的数目
  NB = 8 * sizeof (ulong),
  // 数组最后一个元素的下标
  LI = N == 0 ? 0 : (N - 1) / NB
};
// 存放位向量的数组
ulong A[LI + 1];
\end{cpp}
设置集合元素
\begin{cpp}
template<size_t N>
mySet<N>& mySet<N>::set(size_t P, bool X) {
if (X)  // X为真,位向量中相应值设为1
  A[P / NB] |= (ulong)1 << (P % NB);
// P对应的元素进行按位或运算
else A[P / NB] &= ~((ulong)1 << (P % NB));
  // X为假,位向量中相应值设为0
  return (*this);
}
\end{cpp}
集合的交运算(\&)
\begin{cpp}
template<size_t N>
mySet<N>& mySet<N>::operator&=(const mySet<N>& R)
{ // 赋值交
  for (int i = LI; i >= 0; i--)// 从低位到高位
    A[i] &= R.A[i];    // 以ulong元素为单位按位交
    return (*this);
}
template<size_t N>
mySet<N> operator&(const mySet<N>& L, const mySet<N>& R)
{ //交
  return (mySet<N>(L) &= R);
}
\end{cpp}
\subsection{散列检索}
散列方法的发现得益于计算机寻址，通过将节点的关键码k通过函数h映射为h(k)，h(k)为节点存储的位置。检索的时候也是根据这个函数计算其存储位置。通常散列表的存储是一个一维数组，散列地址是数组的下标。
\textbf{例如}已知线性表的关键码集合为：
\begin{Textcode}
S = {and,array,begin,do,else,end,for,go,if,repeat,then,util,while,while}
\end{Textcode}
可设散列表为：char HT2[26][28]。散列函数H(key)的值，取关键码key中的第一个字母在字母表\{a,b,c,...z\}中的序号，即：H(Key) = key[0]-'a'
\begin{table}[H]
	\centering
	\begin{tabular}{cccc}
		\toprule
		散列地址 & 关键码         & 散列地址 & 关键码          \\
		\midrule
		0    & (and,array) & 13   &              \\
		1    & begin       & 14   &              \\
		2    &             & 15   &              \\
		3    & do          & 16   &              \\
		4    & (end,else)  & 17   & repeat       \\
		5    & for         & 18   &              \\
		6    & go          & 19   & then         \\
		7    &             & 20   & util         \\
		8    & if          & 21   &              \\
		9    &             & 22   & (while,with) \\
		10   &             & 23   &              \\
		11   &             & 24   &              \\
		12   &             & 25   &              \\
		\bottomrule
	\end{tabular}
\end{table}
散列函数的值为key中首尾字母在字母表中序号的平均值,即:
\begin{cpp}
int H3(char key[])
{
    int i = 0;
    while ((i<8) && (key[i]!='\0')) i++;
      return((key[0] + key(i-1) - 2*'a') /2 )
}
\end{cpp}
\begin{table}[H]
	\centering
	\label{H3散列函数下的关键码}
	\begin{tabular}{cccc}
		\toprule
		散列地址 & 关键码   & 散列地址  & 关键码    \\
		\midrule
		0    &       & 13    & while  \\
		1    & and   & 14    & with   \\
		2    &       & 15    & util   \\
		3    & end   & 16    & then   \\
		4    & else  & 17    &        \\
		5    &       & 18    & repeat \\
		6    & if    & 19    &        \\
		7    &       & 20    & begin  \\
		8    & do    & 21    &        \\
		9    &       & 22    &        \\
		10   & go    & 23    &        \\
		11   & for   & 24    &        \\
		12   & array & 25    &        \\
		\bottomrule
	\end{tabular}
\end{table}
\begin{definition}[负载因子：]$\alpha=\frac{n}{m}$,散列表的空间大小为m，填入表中的节点数为n。
\end{definition}
\begin{definition}[冲突：]
	某个散列函数对于部相关的关键码计算出了相同的散列地址。
\end{definition}
\begin{definition}[同义词：]发生冲突的两个关键码。
\end{definition}
\begin{definition}[散列函数：]把关键码值映射到存储位置的函数，通常用h表示。Address=Hash(key)
\end{definition}
散列函数的选取原则：
\begin{itemize}
	\item 运算经可能简单。
	\item 函数的值域必须在表长的范围内。
	\item 尽可能使得关键码不同是，散列函数值不同。
\end{itemize}
需要考虑的因素主要有：关键码长度，散列表大小，关键码分布情况，记录的检索频率。
常用的散列函数选取法：
\begin{itemize}
	\item  除余法
	\item 乘余取整法
	\item 平方取中法
	\item 数字分析法
	\item 基数转换法
	\item 折叠法
	\item ELFhash 字符串散列函数
\end{itemize}
\begin{definition}[除余法：]用关键码x除以M(往往取散列表长度)，并取余数作为散列地址。散列函数为：
	\[h(x)=x\ mod\ M\]
\end{definition}
通常选择一个\textcolor{red}{质数}作为M的值,函数值依赖于自变量x的所有位，不仅仅是最右边k个低位，增大了均匀分布的可能性。M不用偶数，因为如果M设置为偶数：
\begin{itemize}
	\item x是偶数，h(x)也是偶数。
	\item x是奇数，h(x)也是奇数。
\end{itemize}
这样容易导致分布不均匀，因为如果偶数关键码比奇数关键码出现的概率大，那么函数值就不能均匀分布了，反之亦然。M也不用幂：
\begin{figure}[H]
	\centering
	\includegraphics[width=\textwidth]{hash01}
	\caption{幂作为M}
\end{figure}
若把 M 设置为 2 的幂，那么,h(x)=x mod 2，k 仅仅是 x (用二进制表示)最右边的k个位(bit)。 若把 M 设置为 10 的幂那么,h(x)=x mod 10。k 仅仅是 x (用十进制表示)最右边的 k个十进制位(digital)

\textcolor{red}{该散列函数的缺点}:散列值不依赖于x 的全部比特位。
除余法面临的问题：连续的关键码映射成连续的散列值，虽然能保证连续的关键码不发生冲突，但也意味着要占据连续的数组单元。 可能导致散列性能的降低。
\subsection{散列算法}
\subsection*{乘余取整法}
\begin{itemize}
	\item 让关键码key乘上一个常数A(0<A<1),提取其乘积的小数部分。
	\item 用整数n乘上这个值，对结果向下取整，把它作为散列地址。
\end{itemize}
散列函数为：
\[hash(key)=\lfloor n\cdot(A\cdot key\%1\rfloor)\]
其中$A\cdot key\%1$表示$A\cdot key$小数部分：$A\cdot key\%1=A*key-\lfloor A\cdot key\rfloor$
\begin{example}[乘余取整法例子]
	设关键码key = 123456,n = 10000且取$A=\sqrt{5}-1$/2=0.618,因此有：
	\begin{align*}
		has(123456) & =                                                  \\
		            & =\lfloor 1000\cdot(0.6180339\cdot123456\%1)\rfloor \\
		            & =\lfloor 1000\cdot(76300.0041445\ldots\%1)         \\
		            & =41
	\end{align*}
\end{example}
乘余取整法参数取值：
\begin{itemize}
	\item 若地址空间为p位，就取$n=2^p$
	      \begin{itemize}
		      \item 所求的散列地址正好是计算出来的
		      \item $A\cdot key\%1=A\cdot key-\lfloor A\cdot key\rfloor$值的小数点左p bit值
	      \end{itemize}
\end{itemize}
该方法的有点是：n的选择无关紧要。A可以取任何值，和待排序的数组特征有关。一般情况下 A 取黄金分割最理想。

\subsection*{平方取中法}
\begin{definition}[平方取中法]
	先通过关键码的平方扩大差别，再去其中的几位或者其组合作为散列地址。
\end{definition}
\begin{example}[例子]
	\begin{itemize}
		\item 二进制关键码:00000100,00000110,000001010,000001001,000000111
		\item 平方结果为：00010000,00100100,01100010,0101000,1,00110001
		\item 如果表长为4个二进制位，则可取中间四位作为散列地址：（0100,1001,1000,0100,1100）
	\end{itemize}
\end{example}
\textbf{数字分析法}
设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同：
\begin{itemize}
	\item 可能在某些位上分布均匀些，每种符号出现的概率均等。
	\item 在某些位上分布不均匀，只有某集中符号经常出现。
\end{itemize}
可根据散列表的大小，选取其中各个符号分布均匀的若干为作为散列地址。各位数字中符号分布的均匀度$\lambda_k$
\[\lambda_k=\sum_{i=1}^r(\alpha_i^k-\frac{n}{r})^2\]
$\alpha_i^k$表示第i个符号在第k位上出现的次数，$\frac{n}{r}$表示各种符号在n个数中均匀出现的期望值。$\lambda_k$越小，表明该位（第k位）各种符号分布的越均匀。数字分析法仅适用于事先明确知道表中所有关键码每一位数字分布情况，它完全依赖于关键码集合。如果换一个关键码集合，选择哪几位数据要重新决定。
\subsection*{奇数转换法}
把关键码看成是另一进制上的数后再把它转化成原来进制上的数，取其中若干位作为散列地址，一般取大于原来奇数的数作为转换的奇数，并且两个奇数要互质。
\begin{example}[奇数转换法]
	给定一个十进制数的关键码$(210485)_{10}$，把它看成以13为基数的13进制数$(210485)_{13}$，再把它转化成十进制：
	\begin{align}
		(210485)_{13} & =                                                    \\
		              & =2\times 13^5+1\times 13^4+4\times 13^2+8\times 13+5 \\
		              & =(771932)_{10}
	\end{align}
	假设散列表长度为10000,可以取低四位1932作为散列地址。
\end{example}
\subsection*{折叠法}
关键码所含的位数很多，采用平方取中法计算太复杂，使用折叠法：将关键码分割成位数相同的及部分（最有一部分的位数可以不同），然后取这及部分的叠加和（舍去进位）作为散列地址。有两种叠加方法：
\begin{itemize}
	\item 移位叠加：把各部分的最后一位对齐相加。
	\item 分割叠加：各部分不折断，沿着各部分的分解来回折叠，然后对齐相加，将相加的结果作为散列地址。
\end{itemize}
如果一本书的编号为04-42-20586-4
\begin{figure}[H]
	\centering
	% \includegraphics[width=\textwidth]{hash_fold}
	\includesvg[width=\textwidth]{fold_hash_fn}
	\caption{折叠法}
\end{figure}
\textbf{ELFlash字符串散列函数}
用于UNIX系统V4.0"可执行链接格式"：
\begin{cpp}
int ELFhash(char* key) {
  unsigned long h = 0;
  while(*key) {
    h = (h << 4) + *key++;
    unsigned long g = h & 0xF0000000L;
    if (g) h ^= g >> 24;
      h &= ~g;
  }
  return h % M;
}
\end{cpp}
长字符串和短字符串都很有效，字符串中每个字符都有相同的作用，对于散列表中的位置不可能产生不均匀的分布。

\emph{若关键码不是整数而是字符串时，可以把每个字符串转换成整数，再应用平方取中法。}

\subsection{开散列法}
\begin{figure}[H]
	\centering
	\includesvg[width=0.5\textwidth]{open_hash}
	\caption{开散列法}
\end{figure}
表中空单元其实应该有特殊之标记出来，例如使用-1或者INFINITY或者散列表中的内容就是指针，空单元则内容为空指针。

\textbf{开散列法性能分析}：给定一个大小为M存储n个记录的表：散列函数（在理想情况下）将把记录在表中M个位置平均放置，使得平均每一个链表中有n/M个记录。M>n时，散列方法的平均代价为$\Theta(1)$。
\subsection{闭散列法}
$d_0 =h(K)$称为 K 的基地址
\begin{itemize}
	\item 当冲突发生时,使用某种方法为关键码K生成一个散列地址序列 $d_1 ,d_2 ,\ldots d_i ,... , d_{m-1}$ 所有 $d_i (0<i<m)$ 是后继散列地址。
	\item 形成探查的方法不同,所得到的解决冲突的方法也不同。
	\item 插入和检索函数都假定每个关键码的探查序列中至少有一个存储位置是空的，否则可能会陷入一个无限循环中，也可以限制探查序列长度。
\end{itemize}
\subsubsection{线性探查法}
基本思想：如果记录的基位置存储位置被占用,那么就在该位置下面找,找到最后没找到就从头开始找，直到找到一个空存储位置，依次探查下述地址单元：$d+1,d+2,......,M-1,0,1,\ldots,d-1$用于简单线性探查的探查函数是:$P(K,i)=i$。线性探查的优点：表中所有的存储位置都可以作为插入新纪录的候选位置。
\begin{table}[H]
	\centering
	\caption{线性探查例子}
	\begin{tabular}{lllllllllllllll}
		\toprule
		0  & 1  & 2  & 3  & 4  & 5  & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 \\
		\midrule
		26 & 25 & 41 & 15 & 68 & 44 & 6 & 0 & 0 & 0 & 36 & 0  & 38 & 12 & 51 \\
		\bottomrule
	\end{tabular}
	\label{tab:hash_conflict_solve}
\end{table}
\tabref{tab:hash_conflict_solve}因为是线性探查，于对位置11,可能出现该位值是空，插入概率1/15也可能10冲突插入11，总计概率为2/15。

改进线性探查，每次跳过常数c个而不是1个槽，探查序列中的第i个槽是$(h(K)+i) mod M$，基位置相邻的记录就不会进入同一个探查序列了。c和M必须是互为素数。
\subsubsection{二次探查}
探查增量序列地址为:$1^2,-1^2,2^2,-2^2 \ldots$，即地址公式为：
\begin{align*}
d_{2i-1}&=(d+i^2)\%M\\
d_{2i}&=(d-i^2)\%M
\end{align*}
用于简单线性探查的探查函数是：
\begin{equation*}
	\begin{split}
		P(K,2i-1)=i^2\\
		p(K,2i)=-i^2
	\end{split}
\end{equation*}
\begin{remark}
	简单将就是如果地址冲突就先加上$1^2$如果依旧冲突就减去$1^2$(为负就往表后面找)，还冲突就加上$2^2$，还冲突就减去$-2^2$依次直到找到地方放为止。
\end{remark}
\subsubsection{伪随机数序列探查}
查看函数$p(K,i)=perm[i-1]$,这里perm是一个长度为M-1的数组，包含值从1到M-1的随机序列。
\begin{cpp}
//产生n个数的伪随机排列
void permute(int *array,int n)
{
  for(int i=0;i<=n;i++)
    swap(array[i-1],array[Random(i)])
}
\end{cpp}

二次聚集
\begin{itemize}
	\item 消除基本聚集：基地之不同的关键码，其探查序列有所重叠，伪随机探查和二次探查可以消除。
	\item 二次聚集：两个关键码散列到同一个基地址，还是得到同样的严查序列，所产生的聚集，原因是探查序列只是基地址的函数而不是原来关键码值的函数。
\end{itemize}
\subsubsection{双散列探查法的基本思想}
双散列探查法使用两个散列函数$h_1$和$h_2$，若在地址$h_1(key)=d$发生冲突，在计算$h_2(key)$得到的探查序列为：
\[(d+h_2(key))\%M,(d+2h_2)(key))\%M,(d+3h_2(key))\%M,\ldots\]
$h_2(key)$尽量和M互为素数，是发生冲突的同义词地址均匀分布在整个表中，否则可能造成同义词地址的循环计算。优点是不易产生聚集。缺点是计算量增大。

\textbf{M和$h_2(k)$的选择方法}
\begin{itemize}
	\item 方法1：选择M为一个素数，$h_2$返回的值在$1\leq h_2(K)\leq M-1$范围之内。
	\item 方法2：设置$M=2^m$，让$h_2$返回一个1到$2^m$之间的奇数值。
	\item 方法3：若 M 是素数，$h_1(K) = K mod M$,$h_2(k)=k\ mod(M-2)+1$或者$h_2(K)=K\ mod(M-2) +1$.
	\item 方法4：若 M 是任意数，$h_1(K)=K\ mod\ p$(p是小于M的最大素数)。$h_2(K)=K\ mod\ q+1$(q是小于p的最大素数。)
\end{itemize}
